포드-풀커슨 방법(Ford-Fulkerson Method)

- 잔여 네트워크; residual Network

- 확대 경로(증강 경로); Augmenting Path

- 절단

잔여 네트워크가 증강 경로를 더 이상 갖고 있지 않을 때까지 해당 플로우를 반복해서 증가시킨다.

해당 작업이 끝났을 때, 최대 플로우 최소 절단 정리가 최대 플로우를 만듬

잔여 용량 cf(u,v)=⎧⎩⎨⎪⎪c(u,v)−f(u,v)f(v,u)0⎫⎭⎬⎪⎪ $c_f(u, v)=\left\{\begin{array}{cc}c(u, v)-f(u, v)\\f(v, u)\\0\end{array}\right\}$ 증강 (f↑f′)(u,v)={f(u,v)+f′(u,v)0 $(f\uparrow f')(u, v)=\big\{\begin{array}{cc}f(u, v)+f'(u, v)\\0\end{array}$ 상쇄 역방향 간선에 플로우를 보냄 절단 (S, T)의 순 플로우(net flow) f(S,T)=Σu∈SΣv∈Tf(u,v)−Σu∈SΣv∈Tf(v,u) $f(S, T)=\Sigma_{u\in S}\Sigma_{v\in T}f(u, v)-\Sigma_{u\in S}\Sigma_{v\in T}f(v, u)$ 절단 (S, T)의 용량 c(S,T)=Σu∈SΣv∈Tc(u,v) $c(S, T)=\Sigma_{u\in S}\Sigma_{v\in T}c(u, v)$

최대 플로우 최소 절단 정리

잔여 네트워크가 더 이상 증강 경로를 가지지 않을 때, 해당 플로우가 최대가 되며 역도 성립한다.

최소 절단(minimum cut)은 절단 (S, T)의 용량 c(S, T)가 최소가 되는 절단

에드몬드 카프 알고리즘(Emonds Karp Algorithm)

Ford-Fulkerson 방법에서 너비 우선 검색을 통해 증강 경로 p를 존재하는한 계속 발견할 수 있다.

각 간선이 단위 거리 가중치(=1)을 가진다고 할 때, s에서 t까지의 최단 경로를 매번 선택하는 방식으로 구현한

포드-풀커슨 방법을 에드몬드-카프 알고리즘이라고 한다.

O(VE^2)의 시간복잡도를 가짐

introduction to Algorithms 3rd Edition(한글본; Korean Trasistion) pg.743 & pg.744~5 참조

특정 조합문제들은 쉽게 최대 플로우 문제로 전환할 수 있다.

최대 이분 매칭 문제에서 각 간선에 단위 용량(=1)을 할당할 경우, 이는 최대 플로우 문제로 변환된다